package algs4.company;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Iterator;

public class FixedCapacityStack<Item> implements Iterable<Item> {
    private Item[] a;
    private int N;

    public FixedCapacityStack() {
        a = (Item[]) new Object[1];
        a[0] = null;
    }

    void push(Item item) {
        if (N == a.length) resize(a.length * 2);
        a[N++] = item;
    }

    Item pop() {
        Item item = a[--N];
        a[N] = null;
        if (N > 0 && N == a.length / 4) {
            resize(a.length / 2);
        }
        return item;
    }

    boolean isEmpty() {
        return N == 0;
    }

    int size() {
        return N;
    }

    private void resize(int max) {
        Item[] newItemList = (Item[]) new Object[max];
        for (int i = 0; i < N; i++) {
            newItemList[i] = a[i];
        }
        a = newItemList;
    }

    public Iterator<Item> iterator() {
        return new ReverseArrayIterator();
    }

    // 内部类
    class ReverseArrayIterator implements Iterator<Item> {
        private int i = N;

        public boolean hasNext() {
            return i > 0;
        }

        public Item next() {
            return a[--i];
        }
    }

    public static void main(String[] args) {
        FixedCapacityStack<String> stack = new FixedCapacityStack();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) {
                stack.push(item);
            } else if (!stack.isEmpty()) {
                StdOut.print(stack.pop() + " ");
            }
        }
        StdOut.println("(" + stack.size() + " left on stack)");
        for (String item : stack) {
            StdOut.println(item);
        }
    }
}
